package com.boot.sort;

import java.util.Arrays;

public class QuikSort {

    public static void quikSort(int[] arr,int start,int end){

        if(start>=end){
            return;
        }

        int low=start,high=end;
        int pos =arr[low];

        while (low<high){
            while (low<high && arr[high] >=pos){
                high--;
            }
            arr[low] = arr[high];

            while (low<high && arr[low] < pos){
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = pos; //中轴记录到尾 此时 low=high

        quikSort(arr,start,low-1);
        quikSort(arr,low+1,end);
    }

    public static void maoPao(int[] arr){

        for(int i=0;i<arr.length-1;i++){

            boolean is_end=true;
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1] = tmp;
                    is_end=false;
                }
            }

            if(is_end){
                break;
            }
        }
    }

    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {

            int min_idx=i;

            for (int j = i+1; j < arr.length; j++) {
                if(arr[j] < arr[min_idx]){
                    min_idx=j;
                }
            }

            if(min_idx !=i){
                int tmp =arr[i];
                arr[i] =arr[min_idx];
                arr[min_idx] = tmp;
            }
        }
    }

    public static void swap(int[] arr,int i,int j){
        int tmp =arr[i];
        arr[i] = arr[j];
        arr[j] =tmp;
    }

    public static void insertSort(int[] arr){

        for (int i = 1; i < arr.length; i++) {
            for(int j=i;j>0;j--){
                if(arr[j-1]>arr[j]){
                    int tmp =arr[j-1];
                    arr[j-1] =arr[j];
                    arr[j]=tmp;
                }

            }
        }
    }

    public static void quick(int[] arr,int start,int end){
        if(start>=end){
            return;
        }

        int left=start,right=end;
        int pos=arr[left];
        while (left<right){

            while (left<right && arr[right]>=pos){
                right--;
            }
            arr[left]=arr[right];

            while (left<right && arr[left] < pos){
                left++;
            }
            arr[right] = arr[left];

        }
        arr[left] =pos;

        quick(arr,start,left-1);
        quick(arr,left+1,end);
    }

    public static void main(String[] args) {
        int[] a= new int[]{2,4,18,20,3,6,12,20,30,22};
        quick(a,0,a.length-1);
        System.out.println("quick="+Arrays.toString(a));
        a= new int[]{2,4,18,20,3,6,12,20,30,22};
        maoPao(a);
        System.out.println("maopao="+Arrays.toString(a));
        a= new int[]{2,4,18,20,3,6,12,20,30,22};
        selectSort(a);
        System.out.println("selectSort="+Arrays.toString(a));
        a= new int[]{2,4,18,20,3,6,12,20,30,22};
        insertSort(a);
        System.out.println("insertSort="+Arrays.toString(a));

        StringBuilder builder=new StringBuilder();
        builder.append("ss");

        StringBuffer buffer=new StringBuffer();
        buffer.append("ss");
    }
}
